Educational Codeforces Round 96 (Rated for Div. 2)

Educational Codeforces Round 96 (Rated for Div. 2)

Sol

A

我们发现 $3,5,7$ 在 $\mod{3}$ 的意义下取值均不同，那么对于 $n \leq 7$ 特判，否则计算一下再输出。

#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
const int inf = 1e9 + 1e7;
const lint INF = 1e18 + 1e9;

void Solve() {
    int n = readint, a = n / 3, b = 0, c = 0;
    if (n <= 7) {
        if (n == 3) printf("1 0 0\n");
        else if (n == 5) printf("0 1 0\n");
        else if (n == 6) printf("2 0 0\n");
        else if (n == 7) printf("0 0 1\n");
        else puts("-1");
        return ;
    }
    if (n % 3 == 2) ++ b;
    if (n % 3 == 1) ++ c, -- a;
    if (n % 3 == 0) ++ a;
    printf("%d %d %d\n", a - 1, b, c);
    return ;
}

int main(void) {

    int t = readint;
    while (t --) Solve();

    return 0;
}

B

大概做法就是把原序列按从大到小排序后，输出前 $k + 1$ 个数的和。

#include <iostream>
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
const int inf = 1e9 + 1e7, MAXN = 2e5 + 1e1;
const lint INF = 1e18 + 1e9;

lint a[MAXN], Ans;
int n, k;

bool Cmp(lint A, lint B) {
    return A > B;
}

void Solve() {
    n = readint, k = readint, Ans = 0;
    for (int i = 1; i <= n; i ++) a[i] = readlint;
    sort(a + 1, a + n + 1, Cmp);
    for (int i = 1; i <= k + 1; i ++) Ans += a[i];
    printf("%lld\n", Ans);
    return ;
}

int main(void) {

    int t = readint;
    while (t --) Solve();

    return 0;
}

C

大概考虑我们每次合并最大的相邻的两个数，直到最终结果都为 $2$。

#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
const int inf = 1e9 + 1e7;
const lint INF = 1e18 + 1e9;

void Solve() {
    int n = readint;
    if (n == 3) {
        printf("2\n");
        printf("1 3\n");
        printf("2 2\n");
        return ;
    }
    if (n == 2) {
        printf("2\n");
        printf("1 2\n");
        return ;
    }
    if (n & 1) {
        printf("2\n");
        printf("%d %d\n", n, n - 1);
        for (int i = n; i >= 3; i --) {
            printf("%d %d\n", i, i - 2);
        }
    }
    else {
        printf("2\n");
        printf("%d %d\n", n, n - 1);
        for (int i = n; i >= 3; i --) {
            printf("%d %d\n", i, i - 2);
        }
    }
    return ;
}

int main(void) {

    int  t = readint;
    while (t --) Solve();

    return 0;
}

D

每次考虑把最前端的长度大于 $1$ 的相同字符串中删点，直到相同字符串大小全部为 $1$。

#include <iostream>
#include <cstdio>
#include <cctype>
#include <queue>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
const int inf = 1e9 + 1e7, MAXN = 2e5 + 1e1;
const lint INF = 1e18 + 1e9;

int a[MAXN], n, pos, cnt, tot, Ans;
string s;

void Solve() {
    n = readint, cnt = Ans = tot = 0, pos = 1;
    cin >> s;
    a[++ cnt] = 1;
    for (int i = 1; i < n; i ++) {
        if (s[i] == s[i - 1]) ++ a[cnt];
        else a[++ cnt] = 1;
    }
    while (pos <= cnt) {
        if (a[pos] > 1) {
            ++ Ans;
            if (tot > 0) -- a[pos], -- tot;
            else ++ pos;
        }
        else ++ tot, ++ pos;
    }
    printf("%d\n", Ans + (tot / 2) + (tot % 2));
    return ;
}

int main(void) {

    int t = readint;
    while (t --) Solve();

    return 0;
}

E

我们考虑对翻转后的目标字符串的每个字符按照其位置大小赋权，再把对应的权值带回原字符串，然后由于一次操作会使得原字符串的逆序对数减 $1$，那么答案即原字符串赋权后的逆序对数。

#include <iostream>
#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;

template <typename T>
inline T read() {
    T x = 0, f = 1; char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = - f; c = getchar(); }
    while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
    return x * f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read <int> ()
#define readlint read <lint> ()
#define lowbit(x) (x & -x)
const int inf = 1e9 + 1e7, MAXN = 2e5 + 1e1;
const lint INF = 1e18 + 1e9;

struct Operate {
    int p, w;
} op[MAXN];
int a[MAXN], p[26], n, tot;
vector <int> cnt[26];
lint c[MAXN], Ans;
string s;

bool Cmp(Operate A, Operate B) {
    return A.w > B.w;
}

void Modify(int p, int w) {
    for (int i = p; i <= n; i += lowbit(i)) c[i] += 1ll * w;
    return ;
}

lint Query(int p) {
    lint res = 0;
    for (int i = p; i; i -= lowbit(i)) res += c[i];
    return res;
}

int main(void) {

    cin >> n >> s;
    for (int i = n - 1; i >= 0; i --) cnt[s[i] - 'a'].push_back(++ tot);
    for (int i = 0; i < n; i ++) a[i + 1] = cnt[s[i] - 'a'][p[s[i] - 'a'] ++];
    for (int i = 1; i <= n; i ++) op[i] = (Operate){i, a[i]};
    sort(op + 1, op + n + 1, Cmp);
    for (int i = 1; i <= n; i ++) Ans += Query(op[i].p - 1), Modify(op[i].p, 1);
    printf("%lld\n", Ans);

    return 0;
}

Conclusion

1. 很久一段时间后的第一次 CF 比赛，有点赶着图快，策略上出现了严重失误；
2. 做 A 的时间有点长，码力还不太行；
3. 做 C 的时候有点不耐了，实际上应该先思考得到结论后再去写代码，浪费了太多的时间；
4. 由于 CF 的题面是英文的，更应该看清题意，比如做 D 时就没太明白（样例手玩居然也对），直到下考也没能发现我看错了题意（心态崩了）；
5. 贪心很重要。